package org.chnxi.datastructures.sort;

import java.util.Arrays;

public class QuickSorting {
    public static void main(String[] args) {
        int[] arr = {-9,78,0,23,-567,70};

        quickSort(arr , 0, arr.length-1);

        System.out.println(Arrays.toString(arr));

        System.out.println("测试大量数据的执行耗时：");
        int[] randomArr = new int[80000];
        for (int i =0; i<80000; i++){
            randomArr[i] = (int) (Math.random()*80000);
        }

        long start = System.currentTimeMillis();
        quickSort(randomArr , 0 , randomArr.length-1);
        long end = System.currentTimeMillis();
        System.out.println("执行耗时："+(end - start));
    }

    public static void quickSort(int[] arr , int left , int right){
        //做下标
        int l = left;
        //右下标
        int r = right;
        //中轴值
        int pivot = arr[(left+right)/2];
        //临时变量，交换时使用
        int tmp = 0;

        // 1. 让比pivot小的值放到左边
        // 2. 让比pivot大的值放到右边
        while( l < r){
            //在pivot的左边一直找，找到大于等于pivot的值才退出
            while(arr[l] < pivot){
                l += 1;
            }

            //在pivot的右边一直找，找到小于等于pivot的值才退出
            while(arr[r] > pivot){
                r -= 1;
            }
            //说明pivot的只有有两边的值，已经按照左边比pivot小，右边比pivot大于等于
            if(l >= r){
                break;
            }

            //交换
            tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;

            //如果交换完后，发现arr[l] == pivot，r--
            if(arr[l] == pivot){
                r -= 1;
            }

            //如果交换完后，发现arr[r] == pivot，l++
            if(arr[r] == pivot){
                l += 1;
            }
        }

        //如果 l == r，必须l++、r--，否则栈溢出
        if(l == r){
            l += 1;
            r -= 1;
        }

        //向左递归
        if(left < r){
            quickSort(arr , left , r);
        }

        //向右递归
        if(right > l){
            quickSort(arr , l , right);
        }
    }
}
